package leetCode;

import java.util.HashSet;

public class RedundantConnection {
	public int[] findRedundantConnection22(int[][] edges) {
		HashSet<String> edgeSet = new HashSet<>();
		HashSet<Integer> childs = new HashSet<>();
		for (int[] is : edges) {
			if (!childs.add(is[1])) {
				return is;
			}
			String string = is[0] + ":" + is[1];
			if (!edgeSet.add(string)) {
				return is;
			}
			if (edgeSet.contains(is[1] + ":" + is[0])) {
				return is;
			}
		}
		return new int[2];
	}

	public int[] findRedundantConnection(int[][] edges) {
		HashSet<Integer> childs = new HashSet<>();
		HashSet<Integer> parents = new HashSet<>();
		for (int[] is : edges) {
			if (parents.contains(is[0]) && childs.contains(is[1])) {
				return is;
			}
			if (parents.contains(is[1]) && childs.contains(is[0])) {
				return is;
			}
			if (childs.contains(is[0]) && childs.contains(is[1])) {
				return is;
			}
			if (parents.contains(is[0]) && parents.contains(is[1])) {
				return is;
			}
			parents.add(is[0]);
			childs.add(is[1]);
		}
		return new int[2];
	}

	public static void main(String[] args) {
		int[][] edges = { { 2, 3 }, { 5, 2 }, { 1, 5 }, { 4, 2 }, { 4, 1 } };
		int[] res = new RedundantConnection().findRedundantConnection(edges);
		System.out.println(res[0]);
		System.out.println(res[1]);
	}
}
